#include <stdio.h>
#include <stdlib.h>
#define blockSize 1024;//块大小 、 页面大小 为 1kb 1024b;
#define RAM_Size 20*1024;//内存总大小为20MB
#define COUNT 20  // 定义内存块总数 
int PCB_Num;//进程数量
int AvaliableBlcok = COUNT;
enum STATUS {BUSY,FREE//内存块的状态
} block[100]; //建立内存块数组 记录内存信息 
typedef struct Process{//进程
	int PID;//进程ID
	int needSize;//需要的内存大小
	int TotalPage;//总页数
	int blockSze;	//分配的物理块数量
	int pageFaultTimes;//缺页次数
	int accessTimes;//访问地址次数
	struct Process *next;	//指向下一个进程的指针
	struct PageTable *pageTable;//每个进程自己的页表
	struct stackNode *stack;//用于执行LRU算法的栈
}Process,*PCB;
typedef struct PageTable{//页表
	int pageNum;//页表号
	int RAMblockID;//对应的物理块号
	int W;		//页内偏移量
	struct PageTable *next;//下一页
	char State;//用来辨别在内存中还是在外存中 1 = 内存  0 外存
}PageTable,*PageT;
typedef struct stackNode{//栈节点 用来执行LRU算法
	int pageNum;	//页号
	int stackSize;//栈的大小
	struct stackNode *next;
}stack,*P_Stack;
//typedef struct RAM_node{
//	
//};
PageT initPageTable(void);
P_Stack initStack(int stackSize,int pageNum);
void RAMInit()//内存初始化
{
	for(int i=0;i<COUNT;i++)
	{
		block[i] = FREE;
	}
}
PCB initPCB()//进程初始化
{
	PCB head = (PCB)malloc(sizeof(Process));
	head->needSize = 0;
	head->next = NULL;
	head->pageTable = initPageTable();
	head->PID = -1;
	head->stack = NULL;
	head->pageFaultTimes = 0;
	head->accessTimes = 0;
	return head;
}
PageT initPageTable()//页表初始化
{
	PageT head = (PageT)malloc(sizeof(PageTable));
	head->pageNum = -1;
	head->RAMblockID = -1;
	head->W = -1;
	head->next = NULL;
	head->State = '0';
	return head;
}
PageT addPageInfo(PageT head,int PageNum,int RAMblockID,int W)//增加一页
{
	PageT new = (PageT)malloc(sizeof(PageTable));
	new->pageNum = PageNum;
//	new->RAMblockID = RAMblockID;
	new->W = W;
	new->State = '0';
	new->RAMblockID = -1;
	if(head->next == NULL)
	{
		head->next = new;
		new->next = NULL;
		return head;
	}
	PageT p = head->next;
	while(p)
		{
			if(p->next == NULL)
				{
					p->next = new;
					new->next = NULL;
				}
			p = p->next;
		}
	return head;
}
PCB createProcess(PCB head)//创建进程
{
	PCB new = (PCB)malloc(sizeof(Process));
	printf("请输入进程ID:");
	scanf("%d",&new->PID);
	printf("请输入进程需要的内存大小(kb)：");
	int size;
	scanf("%d",&size);
	new->needSize = size * 1024;//B
	new->pageTable = initPageTable();
	new->pageFaultTimes = 0;
	new->accessTimes = 0;
	int PageNum,W = 0;
	W = new->needSize % blockSize;
	PageNum = new->needSize / blockSize;
	new->TotalPage = PageNum;
	int blcokId;
	if(W == 0)
	{
		PageNum -= 1;
	}
	for(int i=0;i<=PageNum;i++)
	{
		if(i ==PageNum)
		{
			W = new->needSize % blockSize;
		}
		else{
			W = 0;
		}
		for(int j=0;j<COUNT;j++)
		{
			if(block[j] == FREE)
			{
				blcokId = j;
//				block[j] = BUSY;
				break;
			}
		}
		addPageInfo(new->pageTable, i, blcokId, W);
	}
		
	if(head->next == NULL)
	{
		head->next = new;
		new->next = NULL;
		return head;
	}
	PCB p = head->next;
	while(p)
	{
		if(p->next == NULL)
		{
			p->next = new;
			new->next = NULL;
		}
		p = p->next;
	}
	return head;
}
PCB deleProcess(PCB head,int PID)
{
	PCB p = head->next;
	if(PID == p->PID)
	{
		head->next = p->next;
		PageT temp = p->pageTable->next;
		while(temp)
		{
			block[temp->RAMblockID] = FREE;
			temp = temp->next;
		}
		free(p);
		return head;
	}
	while(p)
		{
			if(p->next->PID == PID)
				{
					PCB aim = p->next;
					p->next = aim->next;
					free(aim);
				}
			p = p->next;
		}
	return head;
}
void printAllProcess(PCB head)
{
	PCB p = head->next;
	FILE *fp;
	fp = fopen("filename.txt", "a+");  // 以写的方式打开需要写入的文本文件filename
//	fprintf(fp, "%d", a);  // 需要保存的数据为a
	fprintf(fp, "进程ID\t\t占用内存\t\t总页码\t\t内存块大小\t\t缺页率\n");  // 需要保存的数据为a
	printf("进程ID\t\t占用内存\t\t总页码\t\t内存块大小\t\t缺页率\n");
	while(p)
		{
			fprintf(fp, "%d\t\t\t%d\t\t\t%d\t\t\t%d\t\t%f%%\n",p->PID,p->needSize,p->TotalPage,p->blockSze,((float)p->pageFaultTimes / p->accessTimes)*100); 
			printf("%d\t\t\t%d\t\t\t%d\t\t\t%d\t\t%f%%\n",p->PID,p->needSize,p->TotalPage,p->blockSze,((float)p->pageFaultTimes / p->accessTimes)*100);
			PageT temp = p->pageTable->next;
			fprintf(fp, "\t\t\t\t进程%d的页表信息如下\n",p->PID);
			printf("\t\t\t\t进程%d的页表信息如下\n",p->PID);
			fprintf(fp, "\t\t\t\t\t\t\t\t\t\t\t\t\t页码\t\t内存块号\t\t页偏移量\t状态位\n");
			printf("\t\t\t\t\t\t\t\t\t\t\t\t\t页码\t\t内存块号\t\t页偏移量\t状态位\n");
			while(temp)
			{
				fprintf(fp, "\t\t\t\t\t\t\t\t\t\t\t\t\t%d\t\t\t%d\t\t%d\t\t%c\n",temp->pageNum,temp->RAMblockID,temp->W,temp->State);
				printf("\t\t\t\t\t\t\t\t\t\t\t\t\t%d\t\t\t%d\t\t%d\t\t%c\n",temp->pageNum,temp->RAMblockID,temp->W,temp->State);
				temp = temp ->next;
			}
			p = p->next;
			fprintf(fp,"\n");
			printf("\n");
		}
}
void printRAM_State()
{
	printf("内存状态图");
	printf(" ********\n");
	for(int i=0;i<COUNT;i++)
	{
		if(block[i] == BUSY)
			printf("%2d* ## *\n",i);
		else{
			printf("%2d*    *\n",i);
		}
	}
	printf(" ********\n");
}
int getBlcokID()
{
	for(int i=0;i<COUNT;i++)
	{
		if(block[i] == FREE)
		{
			block[i] = BUSY;
			return i;
		}
			
	}
	return -1;//内存已满
}
void allocateRAM_Block(PCB head)//按比例分配，大几率剩余一个内存块
{
	int s = 0;
	PCB p = head->next;
	while (p) {
		s += p->TotalPage;//求出需要内存的总页数
		p = p->next;
	}
//	printf("--%d--\n",s);
	p = head->next;
	while(p)
	{
		p->blockSze = ((float)p->TotalPage/s) * AvaliableBlcok;//按比例分配内存块
		p->stack = initStack(p->blockSze, p->TotalPage);//为需要执行LRU算法的进程分配一个栈结构
//		printf("++%d++\n",p->blockSze);
		p = p->next;
	}
}
P_Stack initStack(int stackSize,int pageNum)//栈的初始化
{
	P_Stack StackHead = (P_Stack)malloc(sizeof(stack));
	StackHead->pageNum = pageNum;
	StackHead->stackSize = stackSize;
	StackHead->next = NULL;
	return StackHead;
}
P_Stack Stack_Push(P_Stack StackHead ,int pageNum,PCB process)//入栈
{
	P_Stack p = StackHead;
	while (p->next) {
		if(p->next->pageNum == pageNum)
			break;
		p = p->next;
	}
	
	if(p == NULL || p->next == NULL)
		{
			P_Stack new =(P_Stack) malloc(sizeof(stack));
			new->pageNum = pageNum;
			new->next = StackHead->next;
			StackHead->next = new;
			process->pageFaultTimes++;
			StackHead->stackSize--;
//			process->blockSze--;
			PageT pt = process->pageTable->next;
			while(pt)
			{
				if(pt->pageNum == pageNum && process->pageTable->RAMblockID == -1)
				{
//					printf("这里");
					pt->State = '1';
					pt->RAMblockID = getBlcokID();
					break;
//					printf("^--%d",pt->RAMblockID);
				}
				else if(pt->pageNum == pageNum && process->pageTable->RAMblockID != -1)
				{
//					printf("哪里");
					pt->State = '1';
					pt->RAMblockID = process->pageTable->RAMblockID;
					process->pageTable->RAMblockID = -1;//把内存块给完就还原为初始值
//					printf("-----------------|||||%d\n",process->pageTable->RAMblockID);//用头节点来存储刚刚被换出去的页面的物理块号
				}
				pt = pt ->next;
			}
			return StackHead;
		}
	
	if(p == StackHead)//或本来就是第一个元素
	{
		return StackHead;
	}
	P_Stack first = StackHead->next;
	P_Stack aim = p->next;
	P_Stack aimNext = aim->next;
	
	StackHead->next = aim;
	aim->next = first;
	p->next = aimNext;
	
	return StackHead;
}
P_Stack Stack_Pop(P_Stack StackHead,int page,PCB process)//出栈
{	
	P_Stack temp = StackHead->next;
	while(temp)
		{
			if(temp->pageNum == page)//如果内存不够了，并且要访问的页还是站里面的页，则不做操作
				break;
			temp = temp->next;
		}
	if(temp!=NULL)
		{
			return StackHead;
		}
	P_Stack p = StackHead->next;
	P_Stack aim = NULL;
	P_Stack pre;
	while(p->next)
		{
			pre = p;
			p = p->next;
		}
	aim = p;
	PageT pt = process->pageTable->next;
	PageT pt2 = process->pageTable->next;
//	printf("-------------------------------%p%p\n",&pt,&pt2);
	while(pt)
	{
		if(pt->pageNum == aim->pageNum)
		{
			pt->State = '0';
			process->pageTable->RAMblockID = pt->RAMblockID;
			pt->RAMblockID = -1;//在外存
//			printf("")
			break;
		}
		pt = pt -> next;
	}
//	printf("-----------------|||||%d\n",pt->RAMblockID);
//	printf("-----------------|||||%d\n",process->pageTable->RAMblockID);//用头节点来存储刚刚被换出去的页面的物理块号
//	printf("我到这里了\n");
//	while(pt2)
//		{
//			if(pt2->pageNum == page)
//				{
//					printf("im here\n");
//					process->pageTable->RAMblockID = pt->RAMblockID;//新页面的内存块指向将要换出页面的内存块
////					printf("----------------------%d\n",pt2->RAMblockID);
//					pt->RAMblockID = -1;//在外存
//					break;
//				}
//			pt2 = pt2 -> next;
//		}
	free(aim);
	pre->next = NULL;
	StackHead->stackSize++;
//	process->blockSze++;
//	printf("----------------------%d\n",pt2->RAMblockID);
	return StackHead;
}
P_Stack LRU(P_Stack StackHead,int page,PCB process)
{
	if(StackHead->stackSize < 1){//先判断栈是否满
		StackHead = Stack_Pop(StackHead,page,process);//满了抛出栈底元素
	}
	StackHead = Stack_Push(StackHead, page,process);//入栈
	P_Stack p = StackHead->next;
	while(p)
	{
		printf("%d\n",p->pageNum);
		p = p->next;
	}
	return StackHead;
}
PCB findProcessById(int id,PCB head)
{
	PCB p = head->next;
	while(p)
	{
		if(p->PID == id)
			return p;
		p = p->next;
	}
	return p;
}
int findAddress(PCB process,int address)
{
	int P = address / blockSize;
	int d = address % blockSize;
	if(P > process->TotalPage){
		printf("地址越界！！！！！！\n");
		return 0;
	}
	process->accessTimes ++;
	PageT aimPage = process->pageTable->next;
	while(aimPage)//查找进程的页表
	{
		if(aimPage->pageNum == P)
			break;
		aimPage= aimPage->next;
	}
	if(aimPage->State == '1')//该页在内存中，直接访问
	{
//		printf("作业了\n");
		int blcokId = aimPage->RAMblockID;
//		printf("************:\n");
//		printf("物理内存地址为:%d\n",address);
//		printf("************:\n");
//		PageT s = process->pageTable->next;
//		while(s)
//			{
//				printf("内存块号为:%d,页表号为:%d\n",s->RAMblockID,s->pageNum);
//				s = s->next;
//			}
//		return blcokId;
	}
	//不在内存，从外存中调入内存
//	printf("不在内存\n");
//	P_Stack StackHead = initStack(process->blockSze,process->TotalPage);
	process->stack = LRU(process->stack, P,process); //执行LRU算法将其调入内存;
	if(d == 0)
	{
		address = (aimPage->RAMblockID + 1) * blockSize ;
	}
	else{
//		printf("id：%d\n",aimPage->RAMblockID);
//		printf("size:%d\n",blockSize);
		int a1 = aimPage->RAMblockID * blockSize;
		address = a1 + d;
	}
	printf("************:\n");
	printf("物理内存地址为:%d\n",address);
	printf("************:\n");
	PageT s = process->pageTable->next;
	while(s)
	{
		printf("内存块号为:%d,页表号为:%d\n",s->RAMblockID,s->pageNum);
		s = s->next;
	}
	return aimPage->RAMblockID;
}
int main(int argc, char *argv[])
{
	PCB ProcessHead = initPCB();
	RAMInit();
	while(1)
	{
		printf("1.创建进程 2.删除进程 3.访问地址 4.查看进程信息\n");
		printf("请输入你的选择：");
		int choose;
		scanf("%d",&choose);
		if(choose == 1)
		{
			printf("请输入你要创建的进程数:");
			scanf("%d",&PCB_Num);
			int n =PCB_Num;
			while(n--)
			{
				ProcessHead = createProcess(ProcessHead);
			}
			allocateRAM_Block(ProcessHead);
			printAllProcess(ProcessHead);
//			printRAM_State();
		}
		else if(choose == 2){
			printAllProcess(ProcessHead);
			printf("请输入你要删除进程的ID：");
			int pid;
			scanf("%d",&pid);
			deleProcess(ProcessHead,pid);
			printf("删除成功！");
			printAllProcess(ProcessHead);
//			printRAM_State();
		}
//		else if(choose == 3)
//		{
//			allocateRAM_Block(ProcessHead);
//			printAllProcess(ProcessHead);
//
//		}
		else if(choose == 3)
		{
			while(1)
			{
			//printAllProcess(ProcessHead);
			printf("请输入你要访问的进程ID(按0结束访问):");
			int id,address;
			scanf("%d",&id);
			if(id == 0)
			{
				break;
			}
			printf("请输入你要访问的内存逻辑地址:");
			scanf("%d",&address);
			findAddress(findProcessById(id, ProcessHead), address);
			printAllProcess(ProcessHead);
			}
		}
		else if(choose == 4)
		{
			printAllProcess(ProcessHead);
		}
	}
	
}